題目說明:給一個非遞減的矩陣(意即陣列當中第i+1個元素數值必>=第i個元素數值)和一個給定的目標值,要你求出該目標值第一次出現和最後一次出現的位置。如果都沒有出現,回傳[-1,-1],題目同時要求時間要控制在O(logn)
Case 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Case 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Case 3:
Input: nums = [], target = 0
Output: [-1,-1]
解題思路:看到要進行搜尋而且時間要控制在O(logn),想必是要使用binary seach(二分搜尋法),關於binary search可以參考之前撰寫的文章。這題比較麻煩的是要求第一次出現和最後一次出現的位置,因此將採用兩次binary search來找出位置。
附上程式碼以及註解
Java
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] result=new int[2];//建立array儲存結果
result[0]=firstpos(nums, target);//搜尋第一次出現的位置
result[1]=lastpos(nums, target);//搜尋最後一次出現的位置
return result;
}
public int firstpos(int[] nums,int target){
int l=0;
int r=nums.length-1;
while (l<=r){
int mid=(l+r)/2;
if (nums[mid]==target){
if (mid>0 && nums[mid-1]==target){
r=mid-1;//要判斷搜尋到的位置是否為第一次出現的位置
}
else{
return mid;
}
}
else if(nums[mid]>target){
r=mid-1;
}
else{
l=mid+1;
}
}
return -1;
}
public int lastpos(int[] nums,int target){
int l=0;
int r=nums.length-1;
while (l<=r){
int mid=(l+r)/2;
if (nums[mid]==target){
if (mid<nums.length-1 && nums[mid+1]==target){
l=mid+1;//要判斷搜尋到的位置是否為最後一次出現的位置
}
else{
return mid;
}
}
else if(nums[mid]>target){
r=mid-1;
}
else{
l=mid+1;
}
}
return -1;
}
}
Python
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def firstpos():
l=0
r=len(nums)-1
while r>=l:
mid=(l+r)//2
if nums[mid]==target:
if mid>0 and nums[mid-1]==target:
r=mid-1 #要判斷搜尋到的位置是否為第一次出現的位置
else:
return mid
elif nums[mid]<target:
l=mid+1
else:
r=mid-1
return -1
def lastpos():
l=0
r=len(nums)-1
while r>=l:
mid=(l+r)//2
if nums[mid]==target:
if mid<len(nums)-1 and nums[mid+1]==target:
l=mid+1 #要判斷搜尋到的位置是否為最後一次出現的位置
else:
return mid
elif nums[mid]<target:
l=mid+1
else:
r=mid-1
return -1
return [firstpos(),lastpos()]